/**
 * @param {number[][]} rects
 */
export var Solution = function (rects) {
  this.rects = rects
  this.sum = [0]
  for (let i = 0; i < rects.length; i++) {
    const [a, b, x, y] = rects[i]
    this.sum.push(this.sum[i] + (x - a + 1) * (y - b + 1))
  }
}

/**
 * @return {number[]}
 */
Solution.prototype.pick = function () {
  let r = Math.ceil(Math.random() * this.sum[this.sum.length - 1])
  const i = this.bisect(this.sum, r)
  const [a, b, x] = this.rects[i - 1]

  r -= this.sum[i - 1] + 1
  const div = x - a + 1
  return [a + (r % div), b + Math.floor(r / div)]
}

Solution.prototype.bisect = function (arr, target) {
  let [left, right] = [0, arr.length - 1]
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (arr[mid] >= target) {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return right
}
/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(rects)
 * var param_1 = obj.pick()
 */
